#include <iostream>
#include <vector>
#include <unordered_map>
#include <stack>
using namespace std;
/**
 * @brief
 * 1 <= nums.length <= 104
-109 <= nums[i] <= 109
 */
class Solution
{
public:
    vector<int> nextGreaterElements(vector<int> &nums)
    {
        int numsLen = nums.size();
        vector<int> ans(numsLen, -1);
        for (int i = 0; i < numsLen; i++)
        {
            int j = i + 1;
            for (; j < numsLen; j++)
            {
                if (nums[j] > nums[i])
                {
                    ans[i] = nums[j];
                    break;
                }
            }
            // search numsLen
            if (j + 1 > numsLen)
            {
                // cout << "circular search" << endl;
                // search 0-i
                j = 0;
                while (j < i)
                {
                    if (nums[j] > nums[i])
                    {
                        ans[i] = nums[j];
                        break;
                    }
                    j++;
                }
            }
        }
        return ans;
    }

    vector<int> nextGreaterElements_2(vector<int> &nums)
    {
        const int numsLen = size(nums);
        stack<int> st{};
        vector<int> result(numsLen, -1);
        for (int i = 0; i < 2 * numsLen; ++i)
        {
            while (!st.empty() && nums[st.top()] < nums[i % numsLen])
            {
                int index = st.top();
                st.pop();
                result[index] = nums[i % numsLen];
            }
            st.push(i % numsLen);
        }
        return result;
    }
};
int main()
{
    /**
     * @brief Test case
     * [-2,1,-3,4,-1,2,1,-5,4]  [1,4,4,-1,2,4,4,4,-1]
     *
     */
    Solution s;
    vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    vector<int> ans = s.nextGreaterElements_2(nums);
    for (int a : ans)
    {
        cout << a << " ";
    }
    cout << endl;
    return 0;
}
